package com.lintcode.solution;

import com.lintcode.solution.entity.Interval;

import java.util.ArrayList;
import java.util.List;

public class Solution_30 {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (intervals == null || intervals.size() == 0) {
            intervals = new ArrayList<>();
            intervals.add(newInterval);
            return intervals;
        }
        List<Interval> result = new ArrayList<>();
        Interval interval1, interval2;
        /*int size = intervals.size();
        for (int i = 0; i < size; i++) {
            interval = intervals.get(i);
            nextInterval = (i + 1) <= (size - 1) ? intervals.get(i + 1) : null;
            if (interval.start > newInterval.start) {
                if (interval.start > newInterval.end) {
                    result.add(newInterval);
                    result.add(interval);
                } else if (interval.end > newInterval.end) {
                    interval.start = newInterval.start;
                    result.add(interval);
                } else if (nextInterval == null || nextInterval.start > newInterval.end) {
                    interval.end = newInterval.end;
                    result.add(interval);
                } else if (nextInterval.end > newInterval.end) {
                    int next = i + 1;
                    while (next < size || nextInterval.end < newInterval.end) {
                        nextInterval = intervals.get(++ next);
                    }
                    if (nextInterval) {
                        interval.end = newInterval.end;
                    }
                    result.add(interval);
                    i++;
                }
            }
        }*/
        int startIndex = 0, endIndex = 0;
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals.get(i).start > newInterval.start || i == (intervals.size() - 1)) {
                startIndex = i;
                break;
            }
        }
        for (int i = startIndex; i < intervals.size(); i++) {
            if (intervals.get(i).start > newInterval.end || i == (intervals.size() - 1)) {
                endIndex = i;
                break;
            }
        }
        interval1 = intervals.get(startIndex - 1);
        interval2 = intervals.get(endIndex);
        
        return result;
    }
}

